In modern society, digital data about individuals can be found relatively easily in the communication networks, especially the Internet. Although the public supports the last decades' advances in digital networks, the sensitive nature of this data motivates the raise of an increasing concern about the public availability of personal data, and the processing performed on it. For instance, in Europe this concern has been reflected in a series of Directives, dealing with the protection of individuals' personal data. Directive 95/46/EC deals with the protection of individuals with regard to the processing of personal data and the free movement of such data, where personal data means any information relating to an identified or identifiable natural person. One of the main ideas of this Directive is that data processing systems must respect the fundamental rights and freedoms, especially the right to privacy. Similar laws and directives regarding informational privacy have been proposed in the US and other developed countries. These include Internet privacy, medical privacy, financial privacy, law enforcement privacy, and political privacy.
There are currently numerous methods available to provide security to a database containing data intended to be held private to third parties. This problem is solved by methods of secure authentication. These methods are widely used to protect the security of databases containing medical, financial, and other types of data. An additional level of security can be added by encrypting all the data contained within the secure database and transmitted to and from the secure database during uploading or downloading operations. This is especially useful when data must be transmitted over a potentially unsecure medium such as computer networks. However, even in these increased security systems at some point the encrypted data is decrypted by an authorized user to perform the necessary data analysis tasks. For instance, in the case of medical research the secure clinical data management system containing the encrypted clinical data and physiological time-series corresponding to a particular study, research, or clinical trial requires the authorized researcher to decrypt the data in order to perform the needed mathematical analysis, signal processing, and statistical analysis in order to generate the study results. There are situations where this conventional framework does not meet the security requirements, that is, in order to analyze and process the encrypted data, such data should not be first decrypted (i.e. the data should be kept encrypted at all times). There are situations where data should be completely private even to researchers, clinical administrators, and system administrators. This may be due to purely privacy reasons or due to research considerations. For instance, certain studies may require scientists and researchers to be completely blinded and the hypothesis and analysis methods to be chosen a-priori. In order to accomplish this, methods for performing the typical mathematical operations and computations including statistical analysis techniques, algebraic methods, signal processing methods, and other computation operations directly on the encrypted datasets are needed. Currently, the availability of such secure methods and cryptosystems is limited.
Conventional cryptographic protocols deal with the problem of protecting some private information from an unauthorized third party that otherwise could modify or have access to the information. In the scenario of secure processing, where the privacy must be preserved not only against an unauthorized third party, but also against the parties that process the data, there are no available systems or methods that can be used in real-world scenarios in terms of both computational cost and communication complexity.
Up to now, the efficient protocols presented in the field of signal processing in the encrypted domain have been focused on linear operations, like scalar products, and non-iterative algorithms. Nevertheless, there are many basic algorithms needed for most signal processing applications that are iterative and involve not only scalar products with known values, but also products between two a-priori unknown sequences. The lack of these algorithms would suppose missing a powerful and irreplaceable tool that enables almost any signal processing application and most types of analysis methods.
Currently there is no practical fully homomorphic cryptosystem, that is, there is no secure cryptosystem that allows for the homomorphic computation of additions and products without restrictions. There has been a recent contribution by Gentry that presents a cryptosystem based on ideal lattices with bootstrappable decryption, and it has been shown that it achieves a full homomorphism. Nevertheless, the authors of this method concede that making the scheme practical remains an open problem.
At the moment there are no cryptosystems available that are capable of performing computations such as solving systems of linear equations without imposing any restrictions on the matrix coefficients. These cryptosystems are a critical building block needed to develop and implement more complex cryptosystems capable of performing advanced signal processing, computation, and analysis directly on encrypted data.